package list;
class Solution {
	public static int MAX = 201;
	public static ListNode[] nodeArr = new ListNode[MAX];
	public static int n;
	public static void arrPattition(int pivot) {
		int small = -1;
		int i = 0;
		while(i!=n) {
			if(nodeArr[i].val < pivot) {
				swap(++small,i++);
			}
			else {
				//nodeArr[i].val >= pivot
				i++;
			}
		}
	}
	
	public class ListNode {
	    int val;
	    ListNode next;

	    ListNode(int x) {
	        val = x;
	        next = null;
	    }
	}

	public static ListNode partition(ListNode head, int pivot) {
	    // 初始化三个部分的头和尾节点指针
	    ListNode smallHead = null, smallTail = null;
	    ListNode equalHead = null, equalTail = null;
	    ListNode bigHead = null, bigTail = null;

	    ListNode next = null; // 用于保存遍历中当前节点的下一个节点

	    // 遍历原始链表
	    while (head != null) {
	        next = head.next; // 保存当前节点的下一个节点
	        head.next = null; // 断开当前节点与链表的连接，便于单独处理

	        // 根据节点值与pivot的关系，将节点分配到对应的部分
	        if (head.val < pivot) {
	            // 小于pivot的部分
	            if (smallTail == null) {
	                smallHead = smallTail = head;
	            } else {
	                smallTail.next = head;
	                smallTail = smallTail.next;
	            }
	        } else if (head.val == pivot) {
	            // 等于pivot的部分
	            if (equalTail == null) {
	                equalHead = equalTail = head;
	            } else {
	                equalTail.next = head;
	                equalTail = equalTail.next;
	            }
	        } else {
	            // 大于pivot的部分
	            if (bigTail == null) {
	                bigHead = bigTail = head;
	            } else {
	                bigTail.next = head;
	                bigTail = bigTail.next;
	            }
	        }

	        head = next; // 移动到下一个节点
	    }

	    // 连接三个部分
	    if (smallTail != null) {
	        smallTail.next = equalHead; // 小于部分的尾连等于部分的头
	        equalTail = equalTail == null ? smallTail : equalTail; // 更新等于部分的尾指针
	    }
	    if (equalTail != null) {
	        equalTail.next = bigHead; // 等于部分的尾连大于部分的头
	    }

	    // 根据是否存在小于部分或等于部分返回合适的头节点
	    return smallHead == null ? (equalHead == null ? bigHead : equalHead) : smallHead;
	}

//	public static void arrPartition(int pivot) {
//		int small = -1;
//		int big = n;
//		int i = 0;
//		while(i!=big) {
//			if(nodeArr[i].val < pivot) {
//				swap(++small,i++);
//			}
//			else if(nodeArr[i].val == pivot) {
//				i++;
//			}
//			else {
//				//nodeArr[i].val > pivot
//				swap(--big,i);
//			}
//		}
//	}
	public static void swap(int i,int j) {
		ListNode temp = nodeArr[i];
		nodeArr[i] = nodeArr[j];
		nodeArr[j] = temp;
	}
//    public ListNode partition(ListNode head, int pivot) {
//        if(head == null) {
//        	return head;
//        }
//        ListNode cur = head;
//        int i = 0;
//        while(cur!=null) {
//        	i++;
//        	cur = cur.next;
//        }
//        n = i;
//        cur = head;
//        for(i=0;i<n;i++) {
//        	nodeArr[i] = cur;
//        	cur = cur.next;
//        }
//        arrPartition(pivot);
//        for(i=1;i<n;i++) {
//        	nodeArr[i-1].next = nodeArr[i];
//        }
//        nodeArr[i-1].next = null;
//        return nodeArr[0];
//    }
}
public class BubbleSortList {

    // 冒泡排序对链表进行排序
    public ListNode bubbleSortList(ListNode head) {
        // 特殊情况处理：空链表或者单节点链表
        if (head == null || head.next == null) {
            return head;
        }

        boolean isSwap; // 标志是否发生过交换
        do {
            isSwap = false; // 每轮遍历开始时重置为false
            ListNode cur = head;
            ListNode prev = null; // 前一个节点指针
            ListNode next = head.next; // 下一个节点指针

            // 遍历链表，进行相邻节点的比较和交换
            while (next != null) {
                if (cur.val > next.val) {
                    // 如果当前节点值大于下一个节点值，交换它们
                    isSwap = true; // 发生交换，标志设为true
                    if (prev == null) {
                        // 处理头节点的情况，直接交换头节点和它的后继节点
                        head = next;
                        cur.next = next.next;
                        next.next = cur;
                    } else {
                        // 对于中间节点的交换
                        prev.next = next;
                        cur.next = next.next;
                        next.next = cur;
                    }
                    // 更新prev和next指针
                    prev = next;
                    next = cur.next;
                } else {
                    // 如果不需要交换，移动到下一个节点
                    prev = cur;
                    cur = next;
                    next = next.next;
                }
            }
        } while (isSwap); // 只要发生交换，继续遍历直到没有交换

        return head; // 返回排序后的链表头节点
    }
}
